import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    //https://leetcode.cn/problems/zigzag-conversion/
    //Z字形变换
    public String convert(String s, int numRows) {
        if(numRows < 2) {
            return s;
        }
        List<StringBuilder> row = new ArrayList<>();
        for(int i = 0; i < numRows;i++) {
            //代表有多少行
            row.add(new StringBuilder());
        }
        char[] ss = s.toCharArray();
        int i = 0,flag = -1;
        for(char ch : ss) {
            row.get(i).append(ch);
            if(i == 0 || i == numRows - 1) {
                //说明到达字符交换的条件了
                //i==0的时候把flag变为整数去加，i == numRows - 1的时候就把flag再赋值为负的进行从大往小的去减少
                flag = -flag;
            }
            i += flag;
        }
        StringBuilder ret = new StringBuilder();
        for(StringBuilder rows : row) {
            ret.append(rows);
        }
        return ret.toString();
    }

    //找到字符串中所有字母异位词
    //优化
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> ret = new ArrayList<>();

        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        for(char ch : pp) {
            //把p的字符一个个放进哈希1中
            hash1[ch - 'a']++;
        }

        int[] hash2 = new int[26];
        int m = pp.length;
        for(int left = 0,right = 0,count = 0; right < ss.length;right++) {
            //我们增加一个变量count，来进行数据的更新操作
            //我们的count代表有效数据的个数
            char in = ss[right];
            //当我们要入窗口的字符自加之后，小于等于我们p里面的数据的个数的话，就是有效的数据，那么我们的count++
            if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if(right - left + 1 > m) {
                //当窗口的长度超过了p的长度的话，我们就进行出窗口操作并且检查count是否需要--
                char out = ss[left++];
                //就相当于我们现在窗口中的是cba再入窗口的e字符，count没有加还是3，
                //当要出c这个字符时候hash1和hash2对应的c这个位置的值是一样的，那么当出c我们的count这个有效字符的个数就要--
                if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            //更新数据
            if(count == m){
                //当count和m相等的时候说明，我们的窗口的字符和p这个字符是一样的，就把窗口的left加入到ret中
                ret.add(left);
            }
        }
        return ret;
    }

    //找到字符串中所有字母异位词
    //https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
    //时间复杂度：O()
    //空间复杂度：O()
    public static boolean check(int[] hash1,int[] hash2) {
        for(int i = 0; i < 26;i++) {
            if(hash1[i] != hash2[i]) {
                return false;
            }
        }
        return true;
    }
    public static List<Integer> findAnagrams(String s, String p) {
        //在s中找p的长度的字符之后进行每个字符的个数的比较，就是可以成功的
        List<Integer> ret = new ArrayList<>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();

        //先把p中的字符都放在数组pp中，记录p中的字符和字符的个数
        int[] hash1 = new int[26];
        for(char ch : pp) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int n = pp.length;
        //进行进窗口和出窗口的操作
        for(int left = 0,right = 0; right < ss.length; right++) {
            //进窗口
            char in = ss[right];
            hash2[in - 'a']++;
            //因为我们只是会超过一位，所以我们只需要出一次窗口即可
            if(right - left + 1 > n) {
                //出窗口
                char out = ss[left++];
                hash2[out - 'a']--;
            }
            if(check(hash1,hash2)) {
                ret.add(left);
            }
        }
        return ret;
    }

    //四数之和
    //https://leetcode.cn/problems/4sum/
    //时间复杂度：O(N^3)
    //空间复杂度：O(logN)
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //和三数之和差不多
        List<List<Integer>> ret = new ArrayList<>();

        //排序
        Arrays.sort(nums);

        int n = nums.length;
        for(int i = 0; i < n;) {
            //我们固定第一个数
            //之后下面就是三数之和
            for(int j = i + 1; j < n;) {
                //再固定一个第一个数后面的数字
                int left = j + 1,right = n - 1;
                //这里的target的值非常大强转成大的类型
                long aim = (long)target - nums[i] - nums[j];
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    if(sum > aim) {
                        right--;
                    }else if (sum < aim) {
                        left++;
                    }else {
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        left++;
                        right--;
                        //去重
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                //第二个固定数去重
                j++;
                while(j < n && nums[j] == nums[j - 1]) j++;
            }
            //第一个固定数去重
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }

    //三数之和
    //https://leetcode.cn/problems/3sum/description/
    //时间复杂度：O(N^2) 两次循环，导致为N^2
    //空间复杂度：O(logN) 因为使用了快速排序，使用的是压栈的方式所以近似为快排的空间复杂度
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();

        //先排序
        Arrays.sort(nums);

        int n = nums.length;
        for(int i = 0; i < n;) {
            //固定的数字必然是负的才能导致最后的结果为0，所以当nums[i] 为 正值就跳出
            if(nums[i] > 0) break;
            //在国定的数的后面找left和right值
            int left = i + 1,right = n - 1,target = -nums[i];
            //这个是国定的数的相反值也就是正数，我们要找的就是left和right这两个数相加等于这个数的值
            //每次固定一个数就要进行遍历后面的值
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum > target) {
                    right--;
                }else if(sum < target) {
                    left++;
                }else {
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    //int[] array = {1,2,3,4,5};
                    //List<Integer> list = Arrays.asList(array);
                    //返回的是java.util.Arrays 的一个内部类 ArrayList，而不是常用的 java.util.ArrayList
                    //Arrays.asList(nums[i],nums[left],nums[right]) 这个方法是将这3个数的数组转换成列表
                    //但是这个返回值不能进行进行正常链表的一系列操作，我们呢可以把其返回值放成构造连链表的参数进行正常的链表操作
                    left++;
                    right--;
                    //去重，我们中间的数可能存在重复的数据，我们要进行去重操作
                    //对我们放进ret之后，我们的left和right的下一个数和我们的放进去的数是不是重复的进行判断
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
            //我们要判断 i 的下一个是否和我们之前检验的数字是一样的，才能再次进行对于上面的运算
            i++;
            //之后我们对于我们固定的数字进行判断是否下一个是重复的
            while(i < n && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> ret = findAnagrams(s,p);
//        int[] nums = {-1,0,1,2,-1,-4};
//        List<List<Integer>> ret = threeSum(nums);
        System.out.println(ret);
    }
}
